package com.lsa.letcode.the120.triangle;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class TriangleTest {
	@Test
	public void test() throws Exception {
		List<List<Integer>> t = Arrays.asList(
				Arrays.asList(2),
				Arrays.asList(3, 4), 
				Arrays.asList(6, 5, 7),
				Arrays.asList(4, 1, 8, 3));
		test(t, 11);
		test(t);
		
		t = Arrays.asList(
				Arrays.asList(2),
				Arrays.asList(4, 3), 
				Arrays.asList(6, 5, 7),
				Arrays.asList(8, 11, 10, 9),
				Arrays.asList(12, 15, 14, 13, 16)
				);
		test(t);
		
		t = Arrays.asList(
				Arrays.asList(10),
				Arrays.asList(10, 0), 
				Arrays.asList(10, 5,  1),
				Arrays.asList(10, 5, 111, 11),
				Arrays.asList(10, 30, 29, 122, 113)
				);
		test(t);
//		Solution s = new Solution();
//		System.out.println(s.minimumTotal(t));
		
//		getAllPathes(4, 0, 0, new LinkedList<Integer>(), new IPathCallBack() {
//			@Override
//			public void pathFound(int r, int c, List<Integer> path) {
//				if (r == 3){
//					System.out.println(path);
//				}
//			}
//		});
	}

	private void test(List<List<Integer>> t, int expected) {
		Solution s = new Solution();
		assertEquals(expected, s.minimumTotal(t));
	}
	
	private void test(final List<List<Integer>> t) {
		Solution s = new Solution();
		final int size = t.size(); 
		final int[] expected = new int[]{Integer.MAX_VALUE};
		@SuppressWarnings("unchecked")
		final List<Integer>[] pathPtr = new List[1];
		getAllPathes(size, 0, 0, new LinkedList<Integer>(), new IPathCallBack() {
			@Override
			public void pathFound(int r, int c, List<Integer> path) {
				if (r == size - 1){
					int sum = 0;
					for (int i = 0; i < path.size(); i++) {
						sum += t.get(i).get(path.get(i));
					}
					if (sum < expected[0]){
						expected[0] = sum;
						pathPtr[0] = new ArrayList<>(path);
					}
				}
			}
		});
		System.out.println(pathPtr[0]);
		assertEquals(expected[0], s.minimumTotal(t));
	}
	
	private void getAllPathes(int n, int r, int c, LinkedList<Integer> path, IPathCallBack pathCallback) {
		if (r == n){
			return;
		}
		
		path.addLast(c);
		pathCallback.pathFound(r, c, path);
		getAllPathes(n, r + 1, c, path, pathCallback);
		getAllPathes(n, r + 1, c + 1, path, pathCallback);
		path.removeLast();
	}
	
	private interface IPathCallBack{
		void pathFound(int r, int c, List<Integer> path);
	}
}